/**
 * @file   BinarySearchTree.h
 * @author Linfufu
 * @date   Tue Nov  2 16:15:29 2021
 * 
 * @brief  
 * 
 * 
 */

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include<bits/stdc++.h>

template <typename Comparable>
class BinarySearchTree
{
 public:
  BinarySearchTree();
  BinarySearchTree( const BinarySearchTree & rhs );
  BinarySearchTree( BinarySearchTree && rhs );
  ~BinarySearchTree();

  const Comparable & findMin() const;
  const Comparable & findMax() const;
  bool contains( const Comparable & x ) const;
  bool isEmpty() const;
  void printTree( std::vector<Comparable> & _data ) const;

  void makeEmpty();
  void insert( const Comparable & x );
  void insert( Comparable && x );
  void remove( const Compable & x );

  BinarySearchTree & operator=( const BinarySearchTree & rhs );
  BinarySearchTree & operator=( BinarySearchTree && rhs );

 private:
  struct BinaryNode
  {
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;

  BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt ):element{ theElement }, left{ lt }, right{ rt } {}

  BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt ):element{ std::move( theElement ) }, left{ lt }, right{ rt }{}
  };

  BinaryNode *root;

  void insert( const Comparable & x, BinaryNode * & t );
  void insert( Comparable && x, BinaryNode * & t );
  void remove( const Comparable & x, BinaryNode * & t );
  BinaryNode * findMin( BinaryNode *t ) const;
  BinaryNode * findMax( BinaryNode *t ) const;
  bool contains( const Comparable & x, BinaryNode *t ) const;
  void makeEmpty( BinaryNode * & t );
  void printTree( BinaryNode *t, std::vector<Comparable> & _data, int & i ) const;
  BinaryNode * clone( BinaryNode *t ) const;
  
};

/* Print the element of the tree */
void printTree( BinaryNode *t, std::vector<Comparable> & _data, int & i ) const;
{
  if( t == nullptr )
    return;
  printTree( t->left, _data, i );
  _data[i] = t ->element;
  i++;
  printTree( t->right, _data, i);
}

void printTree( std::vector<Comparable> & _data ) const
{
  int i = 0;
  printTree( root, _data, i);
}

/* Return true if x is found in the tree */
bool contains( const Comparable & x ) const
{
  return contains( x, root );
};

/* Insert x into the tree;duplicates are ignored */
void insert( const Comparable & x )
{
  insert( x,root )
};

/* Remove x from the tree. Nothing is done if x is not found. */
void remove( const Comparable & x )
{
  remove( x,root);
};

/* Internal method to test if an item is in a subtree. */
/* x is item to search for */
/* t is the node that roots the subtree. */
bool contains( const Comparable & x, BinaryNode *t ) const
{
  if( t == nullptr )
    return false;
  else if( x< t->element )
    return contains( x, t->left );
  else if( t->element < x )
    return contains( x, t->right );
  else
    return true;
};

template <typename Object, typename Comparator= less<Object>>
class BinarySearchTree
{
 public:

 private:

  BinaryNode *root;
  Comparator isLessThan;

  /* Internal method to test if an item is in a subtree. */
  /* x is item to search for. */
  /* t is the node that roots the subtree. */
  bool contains( const Object & x, BinaryNode *t ) const
  {
    if( t == nullptr )
      return false;
    else if( isLessThan( x,t->element ))
      return contains( x, t->left );
    else if( isLessThan( t->element, x ))
      return contains( x, t->right );
    else
      return true;
  };
};

/* Internal method to find the smallest item in a subtree t. */
/* Return node containing the smallest item. */
BinartNode * findMin( BinaryNode *t ) const
{
  if( t == nullpte )
    return nullpter;
  if( t->left == nullptr )
    return t;
  return findMin( t->left );
};

/* Internal method to find the largest item in a subtree t. */
/* Return node containing the largest item. */
BinaryNode * findMax( BinaryNode *t ) const
{
  if( t != nullptr )
    while( t->right != nullptr )
      t = t->right;
  return t;
};

/* Internal method to insert into a subtree. */
/* x is the item to insert. */
/* t is the node that roots the subtree. */
/* Set the new root of the subtree. */
void insert( const Comparable & x, BinaryNode * & t )
{
  if( t== nullptr )
    t = new BinaryNode{ x, nullptr, nullptr };
  else if ( x < t->element )
    insert( x, t->lefy=t );
  else if( t->element < x)
    insert( x, t->right );
  else
    ;
  
};

/* Internal method to insert into a subtree. */
/* x is the item to insert. */
/* t is the node that roots the subtree. */
/* Set the new root of the subtree. */
void insert( const Comparable & x, BinaryNode * & t )
{
  if( t == nullptr )
    t = new BinaryNode{ x, nullptr, nullptr };
  else if( x < t->element )
    insert( x, t->left );
  else if( t->element < x )
    insert( x, t->right );
  else
    ;
};

/* Internal method to insert into a subtree. */
/* x is the item to insert by moving. */
/* t is the node that roots the subtree. */
/* Set the new root of the subtree. */
void insert( Comparable && x, BinaryNode * & t )
{
  if( t == nullptr )
    t = new BinaryNode { std::move( x ), nullptr, nullptr };
  else if( x < t->element )
    insert( std::move( x ), t->left );
  else if( t->element < x)
    insert( std:: move( x ), t->right );
  else
    ;
};

/* Internal method to remove from a subtree. */
/* x is the item to remove. */
/* t is the node that roots the subtree. */
/* Set the new root of the subtree. */
void remove( const Comparable & x, BinaryNode * & t )
{
  if( t == nullptr )
    return;
  if( x < t->element )
    remove( x ,t->left );
  else if( t->element < x)
    remove( x, t->right );
  else if( t->left != nullptr && t->right != nullptr )
  {
    t->element = findMin( t->right )->element;
    remove( t->element, t->right );
  }
  else
  {
    BinaryNode *oldNode = t;
    t = ( t->left != nullptr ) ? t->left : t->right;
    delete oldNode;
  }
  
};


/* Destructor for the tree */
~BinarySearchTree()
{
  makeEmpty();
};

/* Internal method to make subtree empty. */
void makeEmpty( BinaryNode * & t )
{
  if( t != nullptr )
    {
      makeEmpty( t->left );
      makeEmpty( t->right );
      delete t;
    }
  t = nullptr;
};

/* Copy constructor */
BinarySeachTree( const BinarySearchTree & rhs ) : root{nullptr}
{
  root = clone( rhs.root );
}

/* Internal method to clone subtree. */
BinaryNode * clone(BinaryNode *t ) const
{
  if( t== nullptr )
    return nullptr;
  else
    return new BinaryNode{ t->element, clone( t->left ), clone( t->right )
}

#endif
